#include <iostream>
#include <vector>

//思路：从最两侧开始，因为这种情况下，宽度是最大的，所以在两个指针向中间移动的过程中，
//宽度一定变小，所以只有当高度变大的时候才有可能使面积更大，而面积又取决于两个高的
//较小值，所以可以通过单调性来解决问题。

int maxArea(std::vector<int>& v)
{
    int maxArea = 0;
    int left = 0, right = v.size() - 1;
    int width = 0;
    int height = 0;
    while(left < right)
    {
        width = right - left;
        height = std::min(v[left], v[right]);
        if(width * height > maxArea)
        {
            maxArea = width * height;
        }
        if(v[left] < v[right])
        {
            left++;
        }
        else
        {
            right--;
        }
    }
    return maxArea;
}

int maxAreaPractice(std::vector<int>& v)
{
    int ret = 0;
    int left = 0, right = v.size() - 1;
    while(left < right)
    {
        int min = std::min(v[left], v[right]);
        int width = right - left;
        if(ret < width * min)
        {
            ret = width * min;
        }
        if(v[left] < v[right])
        {
            left++;
        }
        else
        {
            right--;
        }
    }
    return ret;
}

int maxAreaPractice2(std::vector<int>& v)
{
    int left = 0, right = v.size() - 1;
    int ret = 0, width = 0;
    while(left < right)
    {
        width = right - left;
        int min = std::min(v[left], v[right]);
        if(ret < width * min)
        {
            ret = width * min;
        }
        if(v[left] < v[right])
        {
            left++;
        }
        else
        {
            right--;
        }
    }
    return ret;
}

int main()
{
    std::vector<int> v = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    std::cout << maxAreaPractice2(v) << std::endl;
    return 0;
}

